#include <iostream>
using namespace std;
class Result
{
public:
	Result()
	{
		x=0;
		y=0;
	}
	Result(int x,int y)
	{
		this->x=x;
		this->y=y;
	}
	void set(int x,int y)
	{
		this->x=x;
		this->y=y;
	}
	void Print()
	{
		cout<<"("<<x<<","<<y<<")"<<endl;
	}
private:
	int x;
    int y;
};
int max(int a,int b)
{
	return a>b?a:b;
}
int max(int a,int b,int c)
{
	return (a>=b&&a>=c)?a:(b>=c?b:c);
}
void DynamicTable(int **M,int *v,int *w,int y,int n)
{
	int i,j;
	for( i=0;i<=n;i++)
	{
		for(int j=0;j<=y;j++)
		{
			M[i][j]=0;
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=y;j++)
		{
			if(j<w[i])
				M[i][j]=M[i-1][j];
			else
				if(j<2*w[i])
					M[i][j]=max(M[i-1][j],M[i-1][j-w[i]]+v[i]);
				else
					M[i][j]=max(M[i-1][j],M[i-1][j-w[i]]+v[i],M[i-1][j-2*w[i]]+2*v[i]);
		}
	}
}
/////////////////////////////////////////////////////
bool PrintResult(int **M,int *v,int *w,int y,int n)
{
	int max=0;
	int i,j,k;
	Result *R=new Result[n];
	for(i=1;i<=n;i++)
	{
		if(M[i][y]>M[max][y])
			max=i;
	}
	if(max==0)
		return false;
	cout<<max<<endl;
	i=max,j=y,k=0;
	do
	{
		while(M[i][j]==M[i-1][j])
		{
			i--;
			if(i==1)
			break;
		}
		if(j-2*w[i]<0)
			{
				R[k++].set(i,1);
				j-=w[i];
			}
		else
			if(M[i-1][j-w[i]]+v[i]>M[i-1][j-2*w[i]]+2*v[i])
			{
				R[k++].set(i,1);
				j-=w[i];
			}
			else
			{
				R[k++].set(i,2);
				j-=2*w[i];
			}
			i--;
	}while(i>0);

	for(i=k-1;i>=0;i--)
	{
		R[i].Print();
	}
	cout<<M[max][y]<<endl;
	return true;
}
void main()
{
	int n=3;
	int y=6;
	int i,j;
	int v[4]={0,6,3,8};
	int w[4]={0,2,3,2};
	int **M=new int*[n+1];
	for(i=0;i<=n;i++)
	{
		M[i]=new int[y+1]; 
	}
	DynamicTable(M,v,w,y,n);
	PrintResult(M,v,w,y,n);
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=y;j++)
			cout<<M[i][j]<<"\t";
		cout<<endl;
	}
}
